#include <stdio.h>
#include <stdlib.h>



int seq_search(int array[] ,int n,int k, int seek_seq[]){
    //在顺序表array[0..n-1]中查找关键字为k的记录
    for (int i = 0;i<n; ++i) {
        seek_seq[i]=i;
        if(array[i]==k){
            return 0;
        }
    }
    return -1;
}

void r(int low,int high,int k,int array[],int *G,int seek_seq[],int location){
    //在按照递增顺序排列的有序表array[0..n-1]中进行二分查找，查找成功时返回0，失败时返回-1；
    //无论查找成功或失败，均通过修改seek_seq参数来返回依次查找的记录位置的序列，seek_seq元素已包含的元素个数等于n
    int middle=(low+high)/2;
    seek_seq[location]=middle;
    location++;
    if(low>high){
        *G=-1;
        return;
        printf("low>high\n");
    }
    if(low==middle){
        *G=high;
        return;
        printf("low==middle\n");
    }
    if(k>array[middle]){
        printf("k>array[middle]\n");
        printf("array[middle]:%d\n",array[middle]);
        printf("---------------\n");
        r(middle+1,high,k,array,&G,seek_seq,location);
    }
    if(k<array[middle]){
        printf("k<array[middle]\n");
        printf("array[middle]:%d\n",array[middle]);
        printf("---------------\n");
        r(low,middle-1,k,array,&G,seek_seq,location);
    }
    if(k==middle){
        printf("k=array[middle]\n");
        printf("array[middle]:%d\n",array[middle]);
        printf("---------------\n");
        *G=middle;
        return;
    }
    return;
}



int bin_search(int array[],int n,int k, int seek_seq[]){
    //在按照递增顺序排列的有序表array[0..n-1]中进行二分查找，查找成功时返回0，失败时返回-1；
    //无论查找成功或失败，均通过修改seek_seq参数来返回依次查找的记录位置的序列，seek_seq元素已包含的元素个数等于n
    int *G;
    r(0,n-1,k,array,&G,seek_seq,0);
    if(G=-1){
        return -1;
    } else
        return G;

}
int main() {

    int n=10;
    int array[] = {0,1,2,3,4,5,6,7,8,9};
    int seek_seq[10] ;

    for (int i = 0; i <n; ++i) {
        seek_seq[i]=-1;
    }
    int c =seq_search(array,n,6,seek_seq);
    printf("%d\n",c);
    for (int i = 0; i <n; ++i) {
        printf("%d,",seek_seq[i]);
    }
    for (int i = 0; i <n; ++i) {
        seek_seq[i]=-1;
    }
    printf("\n");
    int d= bin_search(array,n,4,seek_seq);
    printf("%d\n",d);
    for (int i = 0; i <n; ++i) {
        printf("%d,",seek_seq[i]);
    }
    return 0;
}